import random
class RandomizedSet:
    def __init__(self):
        # dict: val -> list idx
        self.dict = {}
        self.list = []

    def insert(self, val):
        self.list.append(val)
        self.dict[val] = len(self.list) - 1

    def remove(self, val):
        if val in self.dict:
            idx, last_val = self.dict.get(val), self.list[-1]
            self.list[idx] = last_val
            self.dict[last_val] = idx
            self.list.pop()
            del self.dict[val]
            return True
        return False

    def getRandom(self):
        return random.choice(self.list)

randomSet = RandomizedSet()

randomSet.insert(1)

print(randomSet.remove(2))

randomSet.insert(2)

print(randomSet.getRandom())

print(randomSet.remove(1))

randomSet.insert(2)

print(randomSet.getRandom())
